package com.sicheng.lc.杂题.路径问题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/18 20:53
 */
public class 网络延迟时间 {
    //https://leetcode.cn/problems/network-delay-time/
    static int N = 100;
    static int[] dist = new int[N + 1];
    static boolean[] st = new boolean[N + 1];


    {
        Arrays.fill(st, false);
        Arrays.fill(dist, Integer.MAX_VALUE >> 4);
    }

    public int networkDelayTime(int[][] times, int n, int k) {
        ArrayList<int[]>[] g = new ArrayList[n + 1];
        Arrays.setAll(g, m -> new ArrayList<>(n >> 1));
        for (int[] time : times) {
            g[time[0]].add(new int[]{time[1], time[2]});
        }

        int res = 0;
        dist[k] = 0;
        int cnt = 0;
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

        heap.offer(new int[]{k, 0});

        while (!heap.isEmpty()) {
            int[] x = heap.poll();
            int t = x[0];
            int d = x[1];


            if (st[t])
                continue;

            for (int[] p : g[t]) {
                if (!st[p[0]] && p[1] + d < dist[p[0]]) {
                    dist[p[0]] = p[1] + d;
                    heap.offer(new int[]{p[0], dist[p[0]]});
                }
            }
            st[t] = true;
            cnt++;
            res = Math.max(res, dist[t]);

        }

        if (cnt < n)
            return -1;
        return res;
    }

    public static void main(String[] args) {
        网络延迟时间 s = new 网络延迟时间();
        int[][] times = {
                {1, 2, 1}, {2, 1, 3}
        };
        System.out.println(s.networkDelayTime(times, 2, 2));
    }
}
